#include <stdio.h>
#include <stdlib.h>

//二叉排序树新建，中序遍历，查找
typedef int KeyType;
typedef struct BSTNode
{
    KeyType key;
    struct BSTNode *lchild,*rchild;
}BSTNode,*BiTree;

void inset_tree(BiTree &tree, KeyType key)
{
    //申请一个空间
    BiTree newNode=(BiTree)calloc(1,sizeof(BSTNode));
    newNode->key=key;

    //寻找到要插入的位置
    if(NULL == tree)  //判断是否首次插入
    {
        tree=newNode;
        return;
    }
    //tree不为空时
    BiTree temp=tree,parent;
    while(temp != NULL)
    {
        parent=temp;
        if(key < temp->key) //比根节点小就往左子树插入
        {
            temp=temp->lchild;
        }
        else if( key > temp->key)  //比根节点大，往右子树插入
        {
            temp=temp->rchild;
        }
        else //相等则不插入
        {
            return;
        }
    }
    if(key < parent->key)
    {
        parent->lchild=newNode;
    }
    else
    {
        parent->rchild=newNode;
    }

}

void creat_tree(BiTree &tree)
{
    int data[]={54,20,66,40,28,79,58}; //数组存储需要建树的元素
    int len=sizeof(data)/sizeof(data[0]);
    for (int i = 0; i < len; ++i) {
        inset_tree(tree,data[i]);
    }
}

//中序遍历
void InOrder(BiTree tree)
{
    if(NULL == tree)
    {
        return;
    }
    InOrder(tree->lchild);
    printf("%-3d",tree->key);
    InOrder(tree->rchild);
}

//查找
BiTree find_tree(BiTree tree,KeyType key,BiTree &parent)
{
    while(tree != NULL)
    {
        parent =tree;
        if(key < tree->key) //比根节点小就往左子树寻找
        {
            tree=tree->lchild;
        }
        else if( key > tree->key)  //比根节点大，往右子树寻找
        {
            tree=tree->rchild;
        }
        else //相等
        {
            return tree;
        }
    }
    return NULL;
}

//删除某个值
void delete_key(BiTree &tree,KeyType key)
{
    if(NULL == tree){ //空树则无法删除
        return;
    }
    //查找要删除元素的位置
    if(tree->key > key){
        delete_key(tree->lchild,key);  //查找左子树
    }
    else if(tree->key < key){
        delete_key(tree->rchild,key);  //查找右子树
    }
    else
    {
        //找到了要删除的结点
        BiTree temp=tree;
        if(tree->lchild == NULL){ //左子树为空
            tree=tree->rchild;
            free(temp);
            temp=NULL;
        }
        else if(tree ->rchild ==NULL){ //右子树为空
            tree=tree->lchild;
            free(temp);
            temp=NULL;
        }
        else{  //两边子树都不为空
            //寻找当前左树的最右结点 或者 右子树的最左结点
            temp=tree->lchild;
            while(temp->rchild!=NULL){
                temp=temp->rchild;
            }
            tree->key=temp->key;
            delete_key(tree->lchild,temp->key);
        }
    }

}

//删除整个树
void delete_tree(BiTree &tree)
{
    if(NULL == tree)
    {
        return;
    }
    if(tree ->lchild)
    {
        delete_tree(tree->lchild);
    }
    if(tree->rchild)
    {
        delete_tree(tree->rchild);
    }
    free(tree);
    tree=NULL;
}

int main() {
    BiTree tree=NULL;
    creat_tree(tree);  //创建树
    InOrder(tree);
    KeyType key;
    /*BiTree parent=NULL;
    printf("\nplease input key:");
    scanf("%d",&key);
    BiTree pos=find_tree(tree,key,parent);
    if(pos)
    {
        printf("the key is %d\n",pos->key);
    }
    else
    {
        printf("not exist\n");
    }*/
    printf("\nplease input delete key:");
    scanf("%d",&key);
    delete_key(tree,key);
    InOrder(tree);
    delete_tree(tree);
    return 0;
}
